#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int x = 0, y = 0;
        if (matrix[x][y] == target) { return true; }

        for (; x < matrix.size(); ++x) {
            if (x == matrix.size() - 1) { break; }

            if (matrix[x + 1][y] > target) { break; }

            if (matrix[x + 1][y] == target) { return true; }
        }

        for (; y < matrix[x].size(); ++y) {
            if (y == matrix[x].size() - 1) { break; }

            if (matrix[x][y + 1] > target) { break; }

            if (matrix[x][y + 1] == target) { return true; }
        }

        return false;
    }
};